package io.zouyalong.algo.leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/text-justification/
 */
public class TextJustification {
    public static void main(String[] args) {
        var words = new String[]{"What","must","be","acknowledgment","shall","be"};
        var maxWidth = 16;
        var inst = new TextJustification();
        var results = inst.fullJustify(words, maxWidth);
        for (String line : results) {
            System.out.println(line);
        }
    }

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> results = new LinkedList<>();
        List<String> line = new LinkedList<>();
        int lineLen = 0;
        for (String w : words) {
            int newLen = line.size() > 0 ? lineLen + w.length() + 1 : w.length();
            if (newLen < maxWidth) {
                line.add(w);
                lineLen = newLen;
                continue;
            }
            if (newLen == maxWidth) {
                line.add(w);
                results.add(String.join(" ", line));
                line.clear();
                lineLen = 0;
            } else {
                // 当前 word 需要放到下一行
                int restBlank = maxWidth - lineLen;
                int wordsInLine = line.size();
                var lineStr = new StringBuffer();
                lineStr.append(line.get(0));
                int commonBlanks = 0;
                int modBlanks = 0;
                if (wordsInLine > 1) {
                    commonBlanks = restBlank / (wordsInLine-1);
                    modBlanks = restBlank % (wordsInLine - 1);
                } else {
                    for (int i = 0; i < restBlank; i++) {
                        lineStr.append(' ');
                    }
                }
                for (int i = 1; i < wordsInLine; i++) {
                    lineStr.append(' ');
                    for (int j = 0; j < commonBlanks; j++) {
                        lineStr.append(' ');
                    }
                    if (i <= modBlanks) {
                        lineStr.append(' ');
                    }
                    lineStr.append(line.get(i));

                }
                results.add(lineStr.toString());
                line.clear();
                lineLen = 0;
                line.add(w);
                lineLen += w.length();
            }
        }
        if (line.size() > 0) {
            var lineStr = new StringBuffer();
            lineStr.append(String.join(" ", line));
            for (; lineLen < maxWidth; lineLen++) {
                lineStr.append(' ');
            }
            results.add(lineStr.toString());
        }
        return results;
    }
}
